package 动态规划.棋盘dp;

import org.junit.Test;
import utils.ArraySout;
import utils.Mock_Data;

import java.security.spec.RSAOtherPrimeInfo;


/**
 * @author aodre , QQ : 480029069
 * @date 2023/7/5 20:57
 */
public class 左字节笔试 {

    /*
        // 来自字节
    // 给定一个n*m的二维矩阵，每个位置都是字符
    // U、D、L、R表示传送带的位置，会被传送到 : 上、下、左、右
    // . 、O分别表示空地、目标，一定只有一个目标点
    // 可以在空地上选择上、下、左、右四个方向的一个
    // 到达传送带的点会被强制移动到其指向的下一个位置
    // 如果越界直接结束，返回有几个点可以到达O点


     看下做成云的做法!
     BFS
     https://www.bilibili.com/video/BV1Ys4y1k7J8/?spm_id_from=333.788&vd_source=179da737184de5a8f84e4f6c2ee5c350

     ==
     反而我更关心他的 暴力dfs的做法
     */

    /*
   f(i, j) 表示 点(i, j) 能否到达 目标点
   直接记忆化搜索一手!
   少考虑了一种情况!                        ^--------->
                                         |          |
                                         |          |
                                         |         |
                                         <----------v
    有可能 直接走成一个 圈的情况, 这样的话直接 死循环, 这里还需要一个 数组来标记 是否 已经经过(而不是计算过)
    计算过是计算过, 而 经过是经过!
   */
    public static boolean dfs(int i, int j, char[][] martix, Boolean[][] dp, boolean[][] vis) {
        if (i < 0 || i == martix.length || j < 0 || j == martix[0].length) {
            return false; // 越界直接不可达
        }
        if (dp[i][j] != null) {
            return dp[i][j];
        }
        if (martix[i][j] == 'O') {
            return dp[i][j] = true;
        }
        if (vis[i][j]) {  // 这个判断一定要放在 dp判断之后嘛!
            // 如果 点(i, j) dp[i][j] = null还没计算出来, 但是 vis[i][j], 已经走过, 说明什么, 在转圈圈!
            return false;
        }
        boolean ans;
        vis[i][j] = true; // 把当前节点标记 已经走过, 思考一下 **迷宫**, 不做标记的话, 怎么知道自己是不是在转圈 (不能靠 dp 数组来判断)

        switch (martix[i][j]) {
            case 'U':
                ans = dfs(i - 1, j, martix, dp, vis);
                break;
            case 'D':
                ans = dfs(i + 1, j, martix, dp, vis);
                break;
            case 'L':
                ans = dfs(i, j - 1, martix, dp, vis);
                break;
            case 'R':
                ans = dfs(i, j + 1, martix, dp, vis);
                break;
            default:  // 说明当前是 点  " . " ,点的话, 那就有四种方向了
                ans = dfs(i - 1, j, martix, dp, vis) || dfs(i + 1, j, martix, dp, vis) || dfs(i, j - 1, martix, dp, vis) || dfs(i, j + 1, martix, dp, vis);
        }
        vis[i][j] = false;  // 这里一定要要回溯掉
        /*
         如果这里不回溯掉的话, 会出现一些问题!
         即使这里 添加回溯的代码, 这个思路也是错误的!

         - Error Case
            char[][] map = {
                {'.', 'O'},
                {'U', 'U'}
        };

        错误① : 如果没有 回溯 vis[i][j] = false;
       你走一下上面的 流程就明白了

       错误②: 即使添加了回溯代码 : vis[i][j] = false;
        这套算法也是错的!

        在计算 dp[0][0] 的时候, 坐标(0,0) 可有四个决策, 其中 D 这个决策会到 (1,0), 而 (1,0) 又到(0,0) 如果发生 **圈** 的话,会返回false的
        所以 dp[1][0] = false, 会被认为 不可达 O点
        主要原因: dp[0][0] 的其中一个 依赖是 dp[1][0] ,而dp[1][0] 完全依赖 dp[0][0],但是 dp[1][0] 依赖的此时的 dp[0][0] 并不是完全体 决策
        所以导致 dp[1][0]计算失误, 其实这也算是有后效性的存在了!

         */
        return dp[i][j] = ans;

    }

    public static int solve(char[][] martix) {
        int ans = 0;
        Boolean dp[][] = new Boolean[martix.length][martix[0].length];
        boolean vis[][] = new boolean[martix.length][martix[0].length];
        for (int i = 0; i < martix.length; i++) {
            for (int j = 0; j < martix[0].length; j++) {
                if (dfs(i, j, martix, dp, vis)) {
                    ans++;
                }
            }
        }
        ArraySout.printArry(dp);
        return ans;
    }


    // 暴力方法
    // 为了测试
    public static int number1(char[][] map) {
        int ans = 0;
        int n = map.length;
        int m = map[0].length;
        boolean[][] visited = new boolean[n][m];
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[0].length; j++) {
                if (dfs(map, i, j, visited)) {
                    ans++;
                }
            }
        }
        ArraySout.printArry(visited);
        return ans;
    }

    // 暴力方法
    // 为了测试
    public static boolean dfs(char[][] map, int i, int j, boolean[][] visited) {
        if (i < 0 || i == map.length || j < 0 || j == map[0].length || visited[i][j]) {
            return false;
        }
        visited[i][j] = true;
        boolean ans = false;
        if (map[i][j] == 'O') {
            ans = true;
        } else {
            if (map[i][j] == 'U') {
                ans = dfs(map, i - 1, j, visited);
            } else if (map[i][j] == 'D') {
                ans = dfs(map, i + 1, j, visited);
            } else if (map[i][j] == 'L') {
                ans = dfs(map, i, j - 1, visited);
            } else if (map[i][j] == 'R') {
                ans = dfs(map, i, j + 1, visited);
            } else {
                ans = dfs(map, i - 1, j, visited) || dfs(map, i + 1, j, visited) || dfs(map, i, j - 1, visited)
                        || dfs(map, i, j + 1, visited);
            }
        }
        visited[i][j] = false;
        return ans;
    }

    // 正式方法
    // 时间复杂度O(n*m)
    public static int number2(char[][] map) {
        int n = map.length;
        int m = map[0].length;
        boolean[][] visited = new boolean[n][m];
        // queue[i] = {行坐标、列坐标}
        int[][] queue = new int[n * m][2];
        int l = 0;
        int r = 0;
        int ans = 0;
        // O在哪，目的地
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (map[i][j] == 'O') {
                    visited[i][j] = true;
                    queue[r][0] = i;
                    queue[r++][1] = j;
                    break;
                }
            }
        }
        // [] [] [] [] [] ...
        // l ...... r
        while (l < r) { // 队列里还有位置！
            ans++;
            int[] cur = queue[l++];
            int row = cur[0];
            int col = cur[1];
            if (row - 1 >= 0 && !visited[row - 1][col] && (map[row - 1][col] == 'D' || map[row - 1][col] == '.')) {
                visited[row - 1][col] = true;
                queue[r][0] = row - 1;
                queue[r++][1] = col;
            }
            if (row + 1 < n && !visited[row + 1][col] && (map[row + 1][col] == 'U' || map[row + 1][col] == '.')) {
                visited[row + 1][col] = true;
                queue[r][0] = row + 1;
                queue[r++][1] = col;
            }
            if (col - 1 >= 0 && !visited[row][col - 1] && (map[row][col - 1] == 'R' || map[row][col - 1] == '.')) {
                visited[row][col - 1] = true;
                queue[r][0] = row;
                queue[r++][1] = col - 1;
            }
            if (col + 1 < m && !visited[row][col + 1] && (map[row][col + 1] == 'L' || map[row][col + 1] == '.')) {
                visited[row][col + 1] = true;
                queue[r][0] = row;
                queue[r++][1] = col + 1;
            }
        }
        return ans;
    }


    // 为了测试
    public static void main(String[] args) {
        int n = 5;
        int m = 5;
        int testTimes = 10;
        System.out.println("测试开始");
        for (int i = 0; i < testTimes; i++) {
            char[][] map = Mock_Data.genarateRandomMap(n, m);
            int ans1 = number1(map);
            int ans2 = solve(map);
            int ans3 = number2(map);
            if (ans1 != ans2) {
                System.out.println("出错了!");
                System.out.println(ans1 + "  " + ans2 + " " + ans3);
//                ArraySout.printArry(map);

            }
        }
        System.out.println("测试结束");
    }


    @Test
    public void test() {
        char[][] map = {
                {'.', 'O'},
                {'U', 'U'}
        };
        System.out.println(number1(map));
        System.out.println(solve(map));
        System.out.println(number2(map));
    }

}
